NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/1644

Text File | 1996-08-06 | 4.4 KB | 105 lines

Newsgroups: comp.lang.c,comp.lang.c++
Path: ncrgw2.ncr.com!ncrhub6!daynews!falcon!news
From: Dick Menninger <[e-mail]>
Subject: Re: RANDOM NUMBER GENERATOR
X-Nntp-Posting-Host: 149.25.99.44
Message-ID: <[e-mail]>
Sender: [e-mail] (News administrative Login)
Reply-To: [e-mail] (mennid)
Organization: AT&T Global Information Solutions
X-Newsreader: DiscussIT 2.5.1.3 for MS Windows [AT&T Software Products Division]
References: <4cniff$11o$[e-mail]>
Date: Thu, 11 Jan 1996 23:16:02 GMT


> ==========Merlin Chowkwanyun, 1/6/96==========

> Just thought you might like to know that I found this random
> number generator
> lying around in an old C++ magazine

> /declares a global random number generating function

> int random(int MaxVal)
> {
>  return rand() % MaxVal;
> }

> Be sure to include the header file stdlib.h

> Merlin

You can use this as long as you don't mind rather mediocre
results.  There are several things wrong with most of the
discussion in this thread.  The basic wrongs are: using
the same mill for each supposedly independent random
variable; using a composite number [as opposed to a
prime] to mod the mill value.  Using the same mill for all
makes them dependent more than you suspect is likely.
Those games that seem to have patterns of behavior
that occur too frequently often do because of this.
So, get Knuth's Seminumerical Algorithms to learn the
rules for mills.  Mills are half of the problem of a random
variable.  Mapping the mill into a small integer range is the
other half [ignoring floating point, which can reduced to
several integer parts for best results].  This part is easy
to state, but a bitch to prove [partition theory, ...].
Convert your small integer range [lv, hv] to [0, hv-lv].
Get a prime, p, larger than hv-lv.  Use it to mod the mill
value and throw away values larger than hv-lv (i.e.,
recrank the mill).  This produces the best pseudo-random
variable possible with a mill of range X (X usually 2**32
but can now readily be 2**64, a major boon to randomness).
You can even figure out the length of sequence that can
be fully represented [p1, p2, ..., pN] by successive sampling,
and this is major measure of the effective quality.
Solve the equation p**y = X for y and y is the size of the
sequence [this is a hard part to prove].  Consider a prime
near 256.  Its sequence length is about 4 for 32-bit mills.
to get a sequence length around 8, you need a prime range
near 16 for a 32-bit mill, or a 64-bit mill for a prime range
near 256. [This assumes full-cycle mills: see Knuth]

So, to generate really good random variables, you create
separate random variable objects for each random variable.
That means you build a collection of classes to do key parts.
One key part is the ability to create distinct mills. This
is not very hard.  You will need a table of values to use
for the multiplier part [a prime sized table] and separate
mill-based source of odd add parts (the prime size of the
table means that you use every multiplier with every add
before repeating.  Then you use a third mill to create initial
seeds.

Picking the primes for mod-ing either requires a table (with
a search) or a prime sieve algorithm.  I have used both.
I even created my own fast sieve for it.

All of the above is private stuff for the integer random
variable class and needs only exist in its .cpp file.
Of course, you can do it in C without classes if that is
what you have to work with.  In fact, that is how I first
implemented it in the mid-1970s.  But the idea was made
for C++.

Note that separating out your random variables like this
has many noticeable effects.  Consider a game such as
a Rogue variant.  When you think in terms of separate
variables, you now readily control what retry abuses
are available to the player.  Of course, eliminating
one may only create a different one.  But it becomes
a design decision!  In some cases, you may consider pools
of free random vraiables of a given type, IF BOTH:
creation costs are an issue for that type of variable,
and the points at which they would be freed don't
create a bias pattern in their values (proving that
could be interesting ;-) ).  I always generate new ones
and destroy old ones to insure that maximal quality
variables are used (this is theory I am sure of, and
it is easier to do).

Good Day
Dick
[e-mail]